import javax.swing.tree.TreeNode;

class Node{
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }
}

/**
 * 搜索二叉树
 */
public class BinarySearchTree {
    public Node root = null;

    // 查找节点
    public Node search(int key){
//        if (root == null) return null;
//        if (root.val == key) return root;
//        if (root.val < key){
//            root = root.right;
//            search(key);
//        }
//        if (root.val > key){
//            root = root.left;
//            search(key);
//        }
        Node cur = root;
        while (cur != null){
            if (cur.val > key){
                cur = cur.left;
            }else if (cur.val == key){
                return cur;
            }else{
                cur = cur.right;
            }
        }
        return null;
    }

    // 插入节点
    public boolean insert(int val){
        if (root == null){
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = root;
        while (cur != null){
            if (cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if (cur.val < val){
                parent = cur;
                cur = cur.right;
            }else{
                return false;// 不能有相同的 val值
            }
        }
        Node node = new Node(val);
        if (parent.val < val){
            parent.right = node;
        }else{
            parent.left = node;
        }
        return true;
    }

    // 删除节点
    public Node deleteNode(Node root, int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val == key){
                remove(cur,parent);
                break;
            }else if (cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        return root;
    }
    public void remove(Node cur,Node parent){
        if (cur.left == null){
            if (cur == root){
                root = cur.right;
            }else if (cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.left;
            }else if (cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }else{
            Node ta = cur.right;
            Node tap = cur;
            while (ta.left != null){
                tap = ta;
                ta = ta.left;
            }
            cur.val = ta.val;
            remove(ta,tap);
        }
    }
}
